home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Exchess.lha / EXChess / hash.cpp < prev    next >
C/C++ Source or Header  |  1998-08-04  |  9KB  |  321 lines
  1. /*
  2.   Functions dealing with the standard hash table and the pawn hash tables.
  3.   The standard hash table is divided into two pieces.  The lower half uses
  4.   a "smart" replace strategy, and the upper half uses an always replace
  5.   strategy.
  6.   The pawn hash is very much like the standard hash - but simpler.  Only
  7.   the hash key and score is stored.  The pawn table is always replace.
  8. */
  9.  
  10. #include "chess.h"
  11. #include "define.h"
  12. #include "funct.h"
  13. #include "const.h"
  14. #include "hash.h"
  15.  
  16. /* hash table variables */
  17. unsigned long TAB_SIZE = 262144, PAWN_SIZE = 65536;  // hash and pawn hash sizes in entries
  18. hash_rec *hash_table;             // pointer to start of hash table
  19. pawn_rec *pawn_table;             // pointer to start of pawn table
  20. h_code wtm, btm, hval[13][64];    // hash code variables
  21. h_code castle_code[16], ep_code[64], stage_code[4];
  22.  
  23. short h_id = 1;  // hash code id flag for old-current searches
  24.  
  25. extern int null_hash;  // flag for null move from hash table
  26. extern int max_ply;
  27.  
  28. /* Function for or'ing two hash codes */
  29. h_code or(h_code A, h_code B)
  30. {
  31.  h_code temp_code;
  32.  temp_code.address = A.address^B.address;
  33.  temp_code.key = A.key^B.key;
  34.  return temp_code;
  35. }
  36.  
  37. /* Function to set the hash table size */
  38. void set_hash_size(int Mbytes)
  39. {
  40.   unsigned long Tab_entry_size = sizeof(hash_rec);
  41.   unsigned long Pawn_entry_size = sizeof(pawn_rec);
  42.   unsigned long Max_tab_size, Max_pawn_size;
  43.  
  44.   if(Mbytes >= 8) Max_pawn_size = 2000000/(Pawn_entry_size);
  45.   else Max_pawn_size = Mbytes*1000000/(4*Pawn_entry_size);
  46.  
  47.   PAWN_SIZE = 2;
  48.   while(2*PAWN_SIZE < Max_pawn_size) { PAWN_SIZE *= 2; }
  49.  
  50.   Max_tab_size = (Mbytes*1000000 - PAWN_SIZE*Pawn_entry_size)/Tab_entry_size;
  51.  
  52.   TAB_SIZE = 2;
  53.   while(2*TAB_SIZE < Max_tab_size) { TAB_SIZE *= 2; }
  54.  
  55.   close_hash();
  56.   open_hash();
  57. }
  58.  
  59. /* Function with allocates space for the hash tables and generates
  60.    the hash codes */
  61. void open_hash()
  62. {
  63.  start_code();
  64.  hash_table = new hash_rec[TAB_SIZE];
  65.  pawn_table = new pawn_rec[PAWN_SIZE];
  66. }
  67.  
  68. /* function to close the hash table */
  69. void close_hash()
  70. {
  71.  delete [] hash_table;
  72.  delete [] pawn_table;
  73. }
  74.  
  75. /* function to stuff a pawn entry into the pawn table */
  76. void put_pawn(h_code h_key, short score, char wfree_pawn, char bfree_pawn)
  77. {
  78.  pawn_rec *p;
  79.  
  80.  p = pawn_table + (h_key.address&(PAWN_SIZE-1));
  81.  p->key = h_key.key;
  82.  p->score = score;
  83.  p->wfree_pawn = wfree_pawn;
  84.  p->bfree_pawn = bfree_pawn;
  85. }
  86.  
  87. /* function to stuff a hash entry into the hash table */
  88. void put_hash(h_code h_key, int score, int alpha, int beta,
  89.                             int depth, move hmove, int deep)
  90. {
  91.  hash_rec *h; int flag; int ply = max_ply - depth - 1;
  92.  
  93.  // is this an upper bound, lower bound, or exact score?
  94.  if (score >= beta) { flag = FLAG_B; score = beta; }
  95.  else if (score <= alpha) { flag = FLAG_A; score = alpha; hmove.t = NOMOVE; }
  96.  else { flag = FLAG_P; }
  97.  
  98.  // adjust any mate score to be relative to this node.
  99.  if(score >= MATE/2) score += ply;
  100.  else if(score <= -MATE/2) score -= ply;
  101.  
  102.  // find location in table
  103.  h = hash_table + (h_key.address&(TAB_SIZE/2-1));
  104.  
  105.  // use "smart" replace strategy if possible
  106.  if ((h->id != h_id) || (h->depth < depth)
  107.      || (h->depth == depth && (flag > h->flag || (flag == h->flag &&
  108.  ((score > h->score && flag==2) || (score < h->score && flag==1) || flag==3)))))
  109.    {
  110.      h->key = h_key.key;
  111.      h->score = score;
  112.      h->flag = (deep > 2) ? flag : -1;
  113.      h->depth = depth;
  114.      h->hmove = hmove;
  115.      h->id = h_id;
  116.    }
  117.  else   // or use always replace in the upper half of table
  118.    {
  119.      h += TAB_SIZE/2;           // move to upper half of table
  120.      h->key = h_key.key;
  121.      h->score = score;
  122.      h->flag = (deep > 1) ? flag : -1;
  123.      h->depth = depth;
  124.      h->hmove = hmove;
  125.      h->id = h_id;
  126.    }
  127. }
  128.  
  129. /* function to find and return a pawn entry */
  130. int get_pawn(h_code h_key, char *wfree_pawn, char *bfree_pawn)
  131. {
  132.  pawn_rec *p;
  133.  
  134.  p = pawn_table + (h_key.address&(PAWN_SIZE-1));
  135.  if (p->key != h_key.key) return HASH_MISS;
  136.  (*wfree_pawn) = p->wfree_pawn;
  137.  (*bfree_pawn) = p->bfree_pawn;
  138.  return p->score;
  139. }
  140.  
  141. /* function to find and return a hash entry */
  142. int get_hash(h_code h_key, int alpha, int beta, int depth,
  143.                            int *hardalpha, int *hardbeta)
  144. {
  145.  hash_rec *h; int ply = max_ply - depth - 1, hscore;
  146.  
  147.  // find the right location in the table
  148.  h = hash_table + (h_key.address&(TAB_SIZE/2-1));
  149.  
  150.  // check lower part of table first then upper part
  151.  if (h->key != h_key.key)
  152.   { h += TAB_SIZE/2; if (h->key != h_key.key) return HASH_MISS; }
  153.  
  154.  // set null-move switch
  155.  if(h->depth >= depth-2 && (h->flag==FLAG_A || h->flag==FLAG_P)
  156.         && h->score < beta) null_hash = 0;
  157.  
  158.  hscore = h->score;
  159.  
  160.  // Don't trust draw scores
  161.  if(hscore == 0) return HASH_MISS;
  162.  
  163.  // adjust any mate score to be relative to this node.
  164.  if(hscore >= MATE/2) hscore -= ply;
  165.  else if(hscore <= -MATE/2) hscore += ply;
  166.  
  167.  // return hash score if possible, otherwise adjust hardalpha and hardbeta
  168.  if (h->depth < depth) return HASH_MISS; 
  169.  if (h->flag==FLAG_A && hscore <= alpha) return hscore;
  170.  if (h->flag==FLAG_A && depth > -1) (*hardbeta) = hscore;
  171.  if (h->flag==FLAG_B && hscore >= beta) return hscore;
  172.  if (h->flag==FLAG_B && depth > -1) (*hardalpha) = hscore;
  173.  if (h->flag==FLAG_P) return hscore;
  174.  return HASH_MISS;
  175. }
  176.  
  177. /* function to retrieve the hash move from the table */
  178. int get_move(h_code h_key)
  179. {
  180.  hash_rec *h;
  181.  h = hash_table + (h_key.address&(TAB_SIZE/2-1));
  182.  // if the hit was in the upper half of the table, go there
  183.  // check lower part of table first then upper part
  184.  if (h->key != h_key.key)
  185.   { h += TAB_SIZE/2; if (h->key != h_key.key) return NOMOVE; }
  186.  
  187.  return h->hmove.t;
  188. }
  189.  
  190. /* generate the hash code for a given position */
  191. // also calculate material score
  192. h_code gen_code(position *p)
  193. {
  194.   h_code temp_rec = { 0, 0 };
  195.   p->material = 0;
  196.   p->pieces[0] = 0;
  197.   p->pieces[1] = 0;
  198.  
  199.   for(int i = 0; i < 64; i++)
  200.   {
  201.     temp_rec = or(temp_rec, hval[ID(p->sq[i])][i]);
  202.     if(p->sq[i].side == p->wtm) p->material += value[p->sq[i].type];
  203.     else p->material -= value[p->sq[i].type];
  204.     if(p->sq[i].type > PAWN) p->pieces[p->sq[i].side]++;
  205.   }
  206.   if(p->wtm) temp_rec = or(temp_rec, wtm);
  207.   else temp_rec = or(temp_rec, btm);
  208.  
  209.   temp_rec = or(temp_rec, castle_code[p->castle]);
  210.   temp_rec = or(temp_rec, ep_code[p->ep]);
  211.  
  212.   return temp_rec;
  213. }
  214.  
  215. // random number generator
  216. #define IA 16807
  217. #define IM 2147483647
  218. #define AM (1.0/IM)
  219. #define IQ 127773
  220. #define IR 2836
  221. #define NTAB 32
  222. #define NDIV (1+(IM-1)/NTAB)
  223. #define EPS 1.2e-7
  224. #define RNMX (1.0-EPS)
  225.  
  226. float ran(long *idum)
  227. {
  228.    int j;
  229.    long k;
  230.    static long iy=0;
  231.    static long iv[NTAB];
  232.    float temp;
  233.  
  234.    if (*idum <= 0 || !iy) {
  235.        if (-(*idum) < 1) *idum=1;
  236.        else *idum = -(*idum);
  237.        for (j=NTAB+7; j>=0;j--) {
  238.            k=(*idum)/IQ;
  239.            *idum=IA*(*idum-k*IQ)-IR*k;
  240.            if (*idum < 0) *idum += IM;
  241.            if (j < NTAB) iv[j] = *idum;
  242.        }
  243.        iy=iv[0];
  244.    }
  245.    k=(*idum)/IQ;
  246.    *idum=IA*(*idum-k*IQ)-IR*k;
  247.    if (*idum < 0) *idum += IM;
  248.    j=iy/NDIV;
  249.    iy =iv[j];
  250.    iv[j] = *idum;
  251.    if ((temp=AM*iy) > RNMX) return RNMX;
  252.    else return temp;
  253. }
  254.  
  255. /* function to return a random bit */
  256. unsigned long ibit(long *idum)
  257. {
  258.   if (ran(idum) > 0.5) return 1;
  259.   return 0;
  260. }
  261.  
  262. /* function to generate hash codes for all pieces/positions */
  263. void start_code()
  264. {
  265.   long seed1 = -1712913483;
  266.   int i, j, k;
  267.  
  268.   for (i = 0; i < 64; i++)
  269.    { hval[0][i].key = 0; hval[0][i].address = 0; }
  270.   for (j = 1; j < 13; j++)
  271.    {
  272.      for (i = 0; i < 64; i++)
  273.       {
  274.        hval[j][i].key = 0;
  275.        hval[j][i].address = 0;
  276.        for(k = 0; k < 32; k++)
  277.         {
  278.          hval[j][i].key = hval[j][i].key | (ibit(&seed1) << k);
  279.          hval[j][i].address = hval[j][i].address | (ibit(&seed1) << k);
  280.         }
  281.       }
  282.    }
  283.    wtm.address = 0; wtm.key = 0;
  284.    btm.address = 0; btm.key = 0;
  285.    for(k = 0; k < 32; k++) {
  286.     wtm.key = wtm.key | (ibit(&seed1) << k);
  287.     wtm.addr